package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.LinkedList;
import java.util.List;

/**
 * @author feizns
 * @since 2020/3/14
 */
public class FlipMatchVoyage {

    public static void main(String[] args) {
        System.out.println(flipMatchVoyage(create(), new int[]{1, 2, 3}));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.right = new TreeNode(3);
        return ret;
    }

    static int[] v;
    static int index;

    static List<Integer> ret = new LinkedList<>();

    public static List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        v = voyage;
        if ( !pre(root) ) {
            ret.clear();
            ret.add(-1);
        }
        return ret;
    }

    private static boolean pre(TreeNode node) {
        if ( node != null ) {
            if ( node.val != v[index] )
                return false;
            index++;
            if ( node.left != null && node.right != null ) {
                if ( v[index] != node.left.val ) {
                    ret.add(node.val);
                    return pre(node.right) && pre(node.left);
                }
                return pre(node.left) && pre(node.right);
            } else if ( node.left != null )
                return pre(node.left);
            else
                return pre(node.right);
        }
        return true;
    }

}
